Let {an}n=0+∞\left\{a_{n}\right\}_{n=0}^{+\infty} be an infinite sequence of real numbers.

Let {Sn}n=0+∞\left\{S_{n}\right\}_{n=0}^{+\infty} be the sequence of partial sums of {an}n=0+∞\left\{a_{n}\right\}_{n=0}^{+\infty},

sn=∑k=0nak=a0+a1+⋯+an s_{n}=\sum_{k=0}^{n} a_{k}=a_{0}+a_{1}+\cdots+a_{n}

Before we go any further we must

(11) talk about the limit of a seq Ce.

Let {Sn}n=0+∞\left\{S_{n}\right\}_{n=0}^{+\infty} be a sequence of real numbers (infinite).

We say {Sn}n=0+∞\left\{S_{n}\right\}_{n=0}^{+\infty} converges to LL

or

lim⁡n→+∞Sn=L if ∀ε>0,∃N(ε)∈Z+seth ∣Sn−L∣<ε,∀x⩾N \begin{aligned} & \lim _{n \rightarrow+\infty} S_{n}=L \quad \text { if } \\ & \forall \varepsilon>0, \exists N(\varepsilon) \in \mathbb{Z}^{+} \text {seth } \\ & \left|S_{n}-L\right|<\varepsilon, \forall x \geqslant N \end{aligned}

What this means is that the larger that nn gets the chosen sns_{n} gets to L

and we say that Sn→LS_{n} \rightarrow L as x→+∞x \rightarrow+\infty

If there is no number LL sth Sx→LS_{x} \rightarrow L as x→+∞x \rightarrow+\infty we say that the sequence {Sn}n=0+∞\left\{S_{n}\right\}_{n=0}^{+\infty} diverges

(12)(12)

Two improtant limiter

(1) lim⁡n→+∞xn=0\lim _{n \rightarrow+\infty} x^{n}=0 if ∣x∣<1|x|<1

(2) lim⁡n→+∞1n=0\lim _{n \rightarrow+\infty} \frac{1}{n}=0

We have aheady discussed (2) before.

We prove (1) using Bernoulli's inequality

 "1+nh ⩽(1+h)n,∀n=0,1,2,…∥,h>−1 \begin{gathered} \text { "1+nh } \leqslant(1+h)^{n}, \forall n=0,1,2, \ldots \|, \\ h>-1 \end{gathered}

We will see a proof of this inequality later by P. M. I.

case (i) 0<x<10<x<1.

Wite x=11+h,h>0x=\frac{1}{1+h}, h>0

then xn=1(1+h)n⩽11+xh→1a>1bx^{n}=\frac{1}{(1+h)^{n}} \leqslant \frac{1}{1+x h} \quad \begin{array}{ll} & \rightarrow \frac{1}{a}>\frac{1}{b}\end{array}

<1nh <\frac{1}{n h}

Thus ∣xn−0∣=∣xn∣=1(1+h)n<1nh<ε\left|x^{n}-0\right|=\left|x^{n}\right|=\frac{1}{(1+h)^{n}}<\frac{1}{n h}<\varepsilon if nh>1εn h>\frac{1}{\varepsilon}, ie x>1hεx>\frac{1}{h \varepsilon} oR x⩾⌈1hε⌉x \geqslant\left\lceil\frac{1}{h \varepsilon}\right\rceil (13)

for any ε>0\varepsilon>0.

Thus ∀ε>0,xx∣<ε\forall \varepsilon>0, \quad x^{x} \mid<\varepsilon \quad whenever

n⩾⌈1nε⌉,x=11+h n \geqslant\left\lceil\frac{1}{n \varepsilon}\right\rceil \quad, x=\frac{1}{1+h}

case (ii) x=0,xn=0→0x=0, x^{n}=0 \rightarrow 0 as x→+∞x \rightarrow+\infty

case (iii) −1<x<0-1<x<0

then 0<−x<10<-x<1

and −x=11+h,h>0-x=\frac{1}{1+h}, h>0

so

∣xn−0∣=∣xx∣=1(1+h)n<1xh\left|x^{n}-0\right|=\left|x^{x}\right|=\frac{1}{(1+h)^{n}}<\frac{1}{x h} as before

Exevise Show (1)(1) is really "if" by showing ∣x∣⩾1⇒lim⁡n→+∞xn≠0|x| \geqslant 1 \Rightarrow \lim _{n \rightarrow+\infty} x^{n} \neq 0

Returning to infinite series,

We say ∑n=0+∞an\sum_{n=0}^{+\infty} a_{n} converges to LL

and wite ∑n=0+∞an=L\sum_{n=0}^{+\infty} a_{n}=L if

lim⁡n→+∞Sn=lim⁡n→+∞(∑k=0nak)=L \lim _{n \rightarrow+\infty} S_{n}=\lim _{n \rightarrow+\infty}\left(\sum_{k=0}^{n} a_{k}\right)=L

(14)

Thus an infinite series converges the sequence of partial sums converges to a limit.

If ∑n=0+∞an\sum_{n=0}^{+\infty} a_{n} is not convergent,

ie, lim⁡n→+∞Sn\lim _{n \rightarrow+\infty} S_{n} does not exist,

we say ∑n=0+∞an\sum_{n=0}^{+\infty} a_{n} is divergent.

The Infinite Geometric Series

∑k=0+∞ark is convergent iiff∣r∣<1 \sum_{k=0}^{+\infty} a r^{k} \quad \text { is convergent } i_{i f f}|r|<1

Since Gn=∑k=0nark=a(rn+1−1)r−1G_{n}=\sum_{k=0}^{n} a r^{k}=\frac{a\left(r^{n+1}-1\right)}{r-1}

If ∣r∣<1|r|<1, then lim⁡n→+∞Gn=lim⁡n→+∞a(rn+1−1)r−1\lim _{n \rightarrow+\infty} G_{n}=\lim _{n \rightarrow+\infty} \frac{a\left(r^{n+1}-1\right)}{r-1}

=a(0−1)r−1=a1−r \begin{aligned} & =\frac{a(0-1)}{r-1} \\ & =\frac{a}{1-r} \end{aligned}

Thus for ∣r∣<1,∑k=0+∞ark=a1−r|r|<1, \sum_{k=0}^{+\infty} a r^{k}=\frac{a}{1-r}

Eli use this result to chow

0.999⋯=1 0.999 \cdots=1

14a14 a

0.9999⋯=∑k=1∞q10k=9(∑k=19+111)k)=9(110+⋯+1102+⋯+110n+110n+1+⋯ )=910(1+110+1102+⋯ )=910∑k=0∞(110)k=91011−110=910⋅1(910)=1 \begin{aligned} 0.9999 \cdots & =\sum_{k=1}^{\infty} \frac{q}{10^{k}} \\ & \left.=9\left(\sum_{k=1}^{9}+\frac{1}{11}\right)^{k}\right) \\ & =9\left(\frac{1}{10}+\cdots+\frac{1}{10^{2}}+\cdots+\frac{1}{10^{n}}+\frac{1}{10^{n+1}}+\cdots\right) \\ & =\frac{9}{10}\left(1+\frac{1}{10}+\frac{1}{10^{2}}+\cdots\right) \\ & =\frac{9}{10} \sum_{k=0}^{\infty}\left(\frac{1}{10}\right)^{k}=\frac{9}{10} \frac{1}{1-\frac{1}{10}} \\ & =\frac{9}{10} \cdot \frac{1}{\left(\frac{9}{10}\right)}=1 \end{aligned}

(15)

We have shown only the "If" part of own statement.

To prove the "only if" part, we note

for r=1,Gn=a(x+1)→+∞r=1, G_{n}=a(x+1) \rightarrow+\infty as x→+∞x \rightarrow+\infty

so {Gn}n=0+∞\left\{G_{n}\right\}_{n=0}^{+\infty} does not have a limit (it diverges to +∞+\infty ) and ∑k=0+∞a(1)k\sum_{k=0}^{+\infty} a(1)^{k} is divergent,

If ∣r∣>1|r|>1, one can show that lim⁡n→+∞(rn+1)\lim _{n \rightarrow+\infty}\left(r^{n+1}\right) does not exist sene if r>1r>1, these terms get larger and largen positively, while if r<−1,rn+1r<-1, r^{n+1} gets larger and larger in absolute value and it switches from positive to negative and so cant have a limit EXERCISE: What happens when r=−1r=-1 ? ∥\| (16)

Principle of Mathematical Induction (P.M.I.)

Couscher a formal sequence of propositional functions {P(n)}n=1+∞\{P(n)\}_{n=1}^{+\infty}.

We want to be able to prove that the proposition ∀xP(x)\forall x P(x) is True where the universe of discourse for the universal quantifier, ∀\forall, is Z+\mathbb{Z}^{+}.

As some examples of such a proposition we have the 3 summation formulae from before,

(1) ∑k=1nk=n(n+1)2,∀n+Z+\sum_{k=1}^{n} k=\frac{n(n+1)}{2}, \forall n+\mathbb{Z}^{+}

(2) ∑k=1nk2=n(n+1)(2n+1)6,∀n∈Z+\sum_{k=1}^{n} k^{2}=\frac{n(n+1)(2 n+1)}{6}, \forall n \in \mathbb{Z}^{+}

(3) ∑k=1nk3=[n(n+1)2]2,∀n∈Z+\sum_{k=1}^{n} k^{3}=\left[\frac{n(n+1)}{2}\right]^{2}, \forall n \in \mathbb{Z}^{+}

We prove such universally quantified propositions using P.M.I. (7)

P.MI. has 2 steps.

Steel Basis step; prove P(1)P(1) is true.

Step 2 Inductrie step; prove that the proposition

∀k(P(k)→P(k+1))(k≥1) \forall k(P(k) \rightarrow P(k+1)) \quad(k \geq 1)

is tue.

We will prove the validity of PMI. later.

For now consider some examples. At the some time we will be proving useful and important results.

ExT Prove statement (1) above. [ Note, we already gave a direct proof  by showing P(x) is T, fox all x,]\left[\begin{array}{c}\text { Note, we already gave a direct proof } \\ \text { by showing } P(x) \text { is } T \text {, fox all } x,]\end{array}\right.

Let P(n)P(n) be the statement

∑k=1nk=n(n+1)2=f(n) \sum_{k=1}^{n} k=\frac{n(n+1)}{2}=f(n)

Basis Step P(1):∑k=11k=1,f(1)=1(1+1)2=1P(1): \sum_{k=1}^{1} k=1, f(1)=\frac{1(1+1)}{2}=1

∴P(1)\therefore P(1) is tue. (18)

Inductive step

assume Pk(k)P_{k}(k) is tue, k∈Z+(k⩾1)k \in \mathbb{Z}^{+}(k \geqslant 1)

That is ∑l=1kl=k(k+1)2=f(k)\sum_{l=1}^{k} l=\frac{k(k+1)}{2}=f(k).

We show now that P(k+1)P(k+1) io tue, ie, ∑k=1k+1l=f(k+1)\sum_{k=1}^{k+1} l=f(k+1)

But ∑l=1k+1l=∑ℓ=1kl+(k+1)\sum_{l=1}^{k+1} l=\sum_{\ell=1}^{k} l+(k+1)

(=(k+1)(k+2)2) \left(=\frac{(k+1)(k+2)}{2}\right) =k⋅k+1)2+(k+1), by hypothesis. =(k+1)(k2+1)=(k+1)(k+2)2=f(k+1) \begin{aligned} & =\frac{k \cdot k+1)}{2}+(k+1), \text { by hypothesis. } \\ & =(k+1)\left(\frac{k}{2}+1\right) \\ & =\frac{(k+1)(k+2)}{2}=f(k+1) \end{aligned}

Thanes P(k)→P(k+1),∀k∈Z+P(k) \rightarrow P(k+1), \forall k \in \mathbb{Z}^{+}

Hence by PMI,∑k=1nk=n(n+1)2,∀n∈Z+P M I, \sum_{k=1}^{n} k=\frac{n(n+1)}{2}, \forall n \in \mathbb{Z}^{+}

Ex2 Prove (2) above: ∑k=1nk2=n(n+1)(2n+1)6,∀n∈Z\sum_{k=1}^{n} k^{2}=\frac{n(n+1)(2 n+1)}{6}, \forall n \in \mathbb{Z} =f(x)=f(x), say.

Son Basis step,

n=1.∑k=1k2=1;f(1)=1(2)(3)6=1 n=1 . \quad \sum_{k=1} k^{2}=1 ; f(1)=\frac{1(2)(3)}{6}=1

Thus P(1)P(1) is tue. (9)

Inductive step

Assume P(k)P(k) is tue, k∈Z+(k⩾1)k \in \mathbb{Z}^{+}(k \geqslant 1)

Then ∑l=1k+1l2=∑l=1kl2+(k+1)2\sum_{l=1}^{k+1} l^{2}=\sum_{l=1}^{k} l^{2}+(k+1)^{2}

=k(k+1)(2k+1)6+(k+1)2, by =(k+1)[k(2k+1)6+k+1]=(k+1)[2k2+k+6(k+1)6]=(k+1)[2k2+7k+6]6]=(k+1)[2k2+4k+3k+6]6+(k+1)6[2k(k+2)+3(k+2)]=(k+1)(k+2)(2k+3) hypoth =f(k+1) \begin{aligned} & =\frac{k(k+1)(2 k+1)}{6}+(k+1)^{2} \text {, by } \\ & =(k+1)\left[\frac{k(2 k+1)}{6}+k+1\right] \\ & =(k+1)\left[\frac{2 k^{2}+k+6(k+1)}{6}\right] \\ & =(k+1)\left[\frac{\left.2 k^{2}+7 k+6\right]}{6}\right] \\ & =\frac{(k+1)\left[2 k^{2}+4 k+3 k+6\right]}{6}+\frac{(k+1)}{6}[2 k(k+2)+3(k+2)] \\ & =\frac{(k+1)(k+2)(2 k+3)}{\text { hypoth }}=f(k+1) \end{aligned}

∀k∈Z+\forall k \in \mathbb{Z}^{+}

Thus ↑P(k)→P(k+1)\uparrow P(k) \rightarrow P(k+1) is tue and by PMIP M I

P(n)P(n) is tue, ∀n+Z+\forall n+\mathbb{Z}^{+} (20)(20)

Notes 1) a common err in proofs using PMI that lead to an invalid conclusion occurs in the inductive step when we prove P(k)→P(k+1)P(k) \rightarrow P(k+1) is true for k=2,3,4,…k=2,3,4, \ldots, and not for k=1k=1. Then there is no connection between the basis step and the inductive step. This will occur when we have to assume k>1k>1 in a der to prove P(k)→P(k+1)P(k) \rightarrow P(k+1) If P(2)P(2) is false, then we cant conclude ∀nP(n)\forall n P(n).

  1. We may use PMIP M I to prove ∀n⩾n0,P(n)\forall n \geqslant n_{0}, P(n) is tue where n0>1n_{0}>1 by changing the basis step to P(n0)P\left(n_{0}\right) is True, and the inductive step to ∀k⩾n0,P(k)→P(k+1)\forall k \geqslant n_{0}, P(k) \rightarrow P(k+1)

Ex 3 Recall the Harmonic Progression {an}n=1∞\left\{a_{n}\right\}_{n=1}^{\infty} where an=1na_{n}=\frac{1}{n}.

Even though,

lim⁡n→+∞an=lim⁡n→+∞1n=0,  \lim _{n \rightarrow+\infty} a_{n}=\lim _{n \rightarrow+\infty} \frac{1}{n}=0 \text {, }

the Harmonic series ∑n=1+∞1n=1+12+13+⋯+1n+⋯\sum_{n=1}^{+\infty} \frac{1}{n}=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}+\cdots io divergent. (The smaller * smaller bit added infinitely often add up to +∞.1+\infty .1 ) (2)

We will use PMI to help prove this fact Lemma Let Hn=∑k=1n1kH_{n}=\sum_{k=1}^{n} \frac{1}{k}.

Then H2⩾1+x2=f(x),∀n∈Z+H_{2} \geqslant 1+\frac{x}{2}=f(x), \forall n \in \mathbb{Z}^{+}

Proof

Basis step

x=1H2′=1+12=f(1)∴H2⩾f(1) \begin{aligned} & x=1 \\ & H_{2^{\prime}}=1+\frac{1}{2}=f(1) \quad \therefore H_{2} \geqslant f(1) \end{aligned}

Inductive Step

assume H2k⩾1+k2,∀k∈Z+H_{2^{k}} \geqslant 1+\frac{k}{2}, \forall k \in \mathbb{Z}^{+}

Then

H2k+1=∑k=12k+11k=∑r=12k1r+∑k=2k+12k+11r⩾1+k2+12k+1+12k+2+⋯+12k+1=1+k2+12k+1+12k+2+⋯+12k+2k \begin{aligned} H_{2^{k+1}} & =\sum_{k=1}^{2^{k+1}} \frac{1}{k}=\sum_{r=1}^{2^{k}} \frac{1}{r}+\sum_{k=2^{k}+1}^{2^{k+1}} \frac{1}{r} \\ & \geqslant 1+\frac{k}{2}+\frac{1}{2^{k}+1}+\frac{1}{2^{k}+2}+\cdots+\frac{1}{2^{k+1}} \\ & =1+\frac{k}{2}+\frac{1}{2^{k}+1}+\frac{1}{2^{k}+2}+\cdots+\frac{1}{2^{k}+2^{k}} \end{aligned} ⩾1+k2+{12k+2k+⋯+2k terms 2k+2k}( make the  portico bergen  hechion get  smaller )=1+k2+2k⋅12k+1=1+k2+12=1+k+12=f(k+1) \begin{aligned} & \geqslant 1+\frac{k}{2}+\left\{\frac{1}{2^{k}+2^{k}}+\cdots+\frac{2^{k} \text { terms }}{2^{k}+2^{k}}\right\} \quad\left(\begin{array}{l} \text { make the } \\ \text { portico bergen } \\ \text { hechion get } \\ \text { smaller } \end{array}\right) \\ & =1+\frac{k}{2}+2^{k} \cdot \frac{1}{2^{k+1}}=1+\frac{k}{2}+\frac{1}{2}=1+\frac{k+1}{2}=f(k+1) \end{aligned}

(22)

Thus by P,M.1. H2n⩾1+n2,∀n∈Z+H_{2} n \geqslant 1+\frac{n}{2}, \forall n \in \mathbb{Z}^{+}

Now the sequence

{Hn}n=1∞\left\{H_{n}\right\}_{n=1}^{\infty} is an "increasing" sequence

because Hn+1=Hn+1n+1>HnH_{n+1}=H_{n}+\frac{1}{n+1}>H_{n}.

Also the subsequence

{H2n}x=1∞\left\{H_{2^{n}}\right\}_{x=1}^{\infty} clearly, in view of

the lemma, has

lim⁡x→+∞H2x=+∞ \lim _{x \rightarrow+\infty} H_{2 x}=+\infty

These two facts allow us to assent that

lim⁡n→+∞Hn=+∞ and the  \lim _{n \rightarrow+\infty} H_{n}=+\infty \text { and the }

hamonic series is divergent

Exerciser) Use PMI to prove that 3/22n−1,∀x∈Z+3 / 2^{2 n}-1, \forall x \in \mathbb{Z}^{+}

  1. Prove summation formula (3)

P351 #32 3∣n3+2n∀n⩾13 \mid n^{3}+2 n \quad \forall n \geqslant 1

23

P(n):3∣n3+2nP(n): 3 \mid n^{3}+2 n \quad R.T.P. ∀n⩾1P(n)\quad \forall n \geqslant 1 P(n) is the

  1. Basis step

Let n=1,n3+2n=1+2=3+3/3n=1, n^{3}+2 n=1+2=3+3 / 3

∴P(1)\therefore P(1) is true

  1. Inductive Step

want to show

∀k⩾1P(k)→P(k+1)\forall k \geqslant 1 \quad P(k) \rightarrow P(k+1) \quad is tue

Assume 31k3+2k31 k^{3}+2 k ie assume P(k)P(k) is the

Then (k0+1)3+2(k+1)=k3+3k2+3k+1\left(k^{0}+1\right)^{3}+2(k+1)=k^{3}+3 k^{2}+3 k+1

=k3+2k+3k+2=k3+2k divisible by +3(k2+k+1) divisible by 3 \begin{aligned} = & k^{3}+2 k+3 k+2 \\ = & \frac{k^{3}+2 k}{\text { divisible }_{\text {by }}}+\frac{3\left(k^{2}+k+1\right)}{\text { divisible by } 3} \end{aligned}

by hypothein

∴P(k+1)\therefore P(k+1) is tue